//
//  MergeSort.swift
//  Sorts
//
//  Created by lhc on 2023/12/10.
//

import Foundation

class MergeSort: BaseSort {
    
    var action: ((OperatorType, (Int, Int)) -> ())?
    
    func sort() {
        self.recurisonSort(left: 0, right: self.array.count - 1)
    }
    
    private func recurisonSort(left: Int, right: Int) {
        guard left < right else {return}
        
        let mid = left + (right - left) / 2
        self.recurisonSort(left: left, right: mid)
        self.recurisonSort(left: mid + 1, right: right)
        
        if self.array[mid] > self.array[mid + 1] {
            self.merge(left: left, mid: mid, right: right)
        }
    }
    
    private func merge(left: Int, mid: Int, right: Int) {
        
        let temporaryArray = Array(self.array[left...right])
        
        var n = left
        var i = left
        var j = mid + 1
        
        while n <= right {
            if i > mid {
                array[n] = temporaryArray[j - left]
                execute(n: n, value: array[n])
                j += 1
            }
            else if j > right {
                array[n] = temporaryArray[i - left]
                execute(n: n, value: array[n])
                i += 1
            }
            else if temporaryArray[i - left] <= temporaryArray[j - left] {
                array[n] = temporaryArray[i - left]
                execute(n: n, value: array[n])
                i += 1
            }
            else if temporaryArray[i - left] > temporaryArray[j - left] {
                array[n] = temporaryArray[j - left]
                execute(n: n, value: array[n])
                j += 1
            }
            n += 1
        }
    }
    
    private func execute(n: Int, value: Int) {
        guard let action = action else {return}
        
        action(.assign, (n, value))
    }
}
